package find.duplicate.subtrees;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @Time 2020/1/01
 * @author 王光浩
 * @Need 给出一个棵二叉树，找出二叉树上所有具有相同结构，且每一个节点值对应相等的子树，结果只需返回一个具有
 *       这种相同结构子树的根节点。
 * @Method 序列化二叉树。每一个节点的序列化结果都是不一致的，除了符合题目要求的根节点。
 */
public class OthersMethod {
	Map<String,Integer> count;
	List<TreeNode> result;
	public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
		count=new HashMap<String,Integer>();
		result=new LinkedList<TreeNode>();
		this.collect(root);
		return result;
	}
	/**对将每一个节点进行序列化（使用深度优先搜索）*/
	private String collect(TreeNode node) {
		if(node==null)return "#";             //形成一个满二叉树二叉树
		String serial=node.val+","+collect(node.left)+","+collect(node.right); //使用深度优先搜索
		count.put(serial, count.getOrDefault(serial, 0)+1);
		if(count.get(serial)==2) {
			result.add(node);
		}
		return serial;
	}
}
